Jump to content

k-regular sequence

From Wikipedia, the free encyclopedia

In mathematics and theoretical computer science, a k-regular sequence is a sequence satisfying linear recurrence equations that reflect the base-k representations of the integers. The class of k-regular sequences generalizes the class of k-automatic sequences to alphabets of infinite size.

Definition

[edit]

There exist several characterizations of k-regular sequences, all of which are equivalent. Some common characterizations are as follows. For each, we take R′ to be a commutative Noetherian ring and we take R to be a ring containing R′.

k-kernel

[edit]

Let k ≥ 2. The k-kernel of the sequence is the set of subsequences

The sequence is (R′, k)-regular (often shortened to just "k-regular") if the -module generated by Kk(s) is a finitely-generated R′-module.[1]

In the special case when , the sequence is -regular if is contained in a finite-dimensional vector space over .

Linear combinations

[edit]

A sequence s(n) is k-regular if there exists an integer E such that, for all ej > E and 0 ≤ rjkej − 1, every subsequence of s of the form s(kejn + rj) is expressible as an R′-linear combination , where cij is an integer, fijE, and 0 ≤ bijkfij − 1.[2]

Alternatively, a sequence s(n) is k-regular if there exist an integer r and subsequences s1(n), ..., sr(n) such that, for all 1 ≤ ir and 0 ≤ ak − 1, every sequence si(kn + a) in the k-kernel Kk(s) is an R′-linear combination of the subsequences si(n).[2]

Formal series

[edit]

Let x0, ..., xk − 1 be a set of k non-commuting variables and let τ be a map sending some natural number n to the string xa0 ... xae − 1, where the base-k representation of x is the string ae − 1...a0. Then a sequence s(n) is k-regular if and only if the formal series is -rational.[3]

Automata-theoretic

[edit]

The formal series definition of a k-regular sequence leads to an automaton characterization similar to Schützenberger's matrix machine.[4][5]

History

[edit]

The notion of k-regular sequences was first investigated in a pair of papers by Allouche and Shallit.[6] Prior to this, Berstel and Reutenauer studied the theory of rational series, which is closely related to k-regular sequences.[7]

Examples

[edit]

Ruler sequence

[edit]

Let be the -adic valuation of . The ruler sequence (OEISA007814) is -regular, and the -kernel

is contained in the two-dimensional vector space generated by and the constant sequence . These basis elements lead to the recurrence relations

which, along with the initial conditions and , uniquely determine the sequence.[8]

Thue–Morse sequence

[edit]

The Thue–Morse sequence t(n) (OEISA010060) is the fixed point of the morphism 0 → 01, 1 → 10. It is known that the Thue–Morse sequence is 2-automatic. Thus, it is also 2-regular, and its 2-kernel

consists of the subsequences and .

Cantor numbers

[edit]

The sequence of Cantor numbers c(n) (OEISA005823) consists of numbers whose ternary expansions contain no 1s. It is straightforward to show that

and therefore the sequence of Cantor numbers is 2-regular. Similarly the Stanley sequence

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (sequence A005836 in the OEIS)

of numbers whose ternary expansions contain no 2s is also 2-regular.[9]

Sorting numbers

[edit]

A somewhat interesting application of the notion of k-regularity to the broader study of algorithms is found in the analysis of the merge sort algorithm. Given a list of n values, the number of comparisons made by the merge sort algorithm are the sorting numbers, governed by the recurrence relation

As a result, the sequence defined by the recurrence relation for merge sort, T(n), constitutes a 2-regular sequence.[10]

Other sequences

[edit]

If is an integer-valued polynomial, then is k-regular for every .

The Glaisher–Gould sequence is 2-regular. The Stern–Brocot sequence is 2-regular.

Allouche and Shallit give a number of additional examples of k-regular sequences in their papers.[6]

Properties

[edit]

k-regular sequences exhibit a number of interesting properties.

  • Every k-automatic sequence is k-regular.[11]
  • Every k-synchronized sequence is k-regular.
  • A k-regular sequence takes on finitely many values if and only if it is k-automatic.[12] This is an immediate consequence of the class of k-regular sequences being a generalization of the class of k-automatic sequences.
  • The class of k-regular sequences is closed under termwise addition, termwise multiplication, and convolution. The class of k-regular sequences is also closed under scaling each term of the sequence by an integer λ.[12][13][14][15] In particular, the set of k-regular power series forms a ring.[16]
  • If is k-regular, then for all integers , is k-automatic. However, the converse does not hold.[17]
  • For multiplicatively independent kl ≥ 2, if a sequence is both k-regular and l-regular, then the sequence satisfies a linear recurrence.[18] This is a generalization of a result due to Cobham regarding sequences that are both k-automatic and l-automatic.[19]
  • The nth term of a k-regular sequence of integers grows at most polynomially in n.[20]
  • If is a field and , then the sequence of powers is k-regular if and only if or is a root of unity.[21]

Proving and disproving k-regularity

[edit]

Given a candidate sequence that is not known to be k-regular, k-regularity can typically be proved directly from the definition by calculating elements of the kernel of and proving that all elements of the form with sufficiently large and can be written as linear combinations of kernel elements with smaller exponents in the place of . This is usually computationally straightforward.

On the other hand, disproving k-regularity of the candidate sequence usually requires one to produce a -linearly independent subset in the kernel of , which is typically trickier. Here is one example of such a proof.

Let denote the number of 's in the binary expansion of . Let denote the number of 's in the binary expansion of . The sequence can be shown to be 2-regular. The sequence is, however, not 2-regular, by the following argument. Suppose is 2-regular. We claim that the elements for and of the 2-kernel of are linearly independent over . The function is surjective onto the integers, so let be the least integer such that . By 2-regularity of , there exist and constants such that for each ,

Let be the least value for which . Then for every ,

Evaluating this expression at , where and so on in succession, we obtain, on the left-hand side

and on the right-hand side,

It follows that for every integer ,

But for , the right-hand side of the equation is monotone because it is of the form for some constants , whereas the left-hand side is not, as can be checked by successively plugging in , , and . Therefore, is not 2-regular.[22]

Notes

[edit]
  1. ^ Allouche and Shallit (1992), Definition 2.1.
  2. ^ a b Allouche & Shallit (1992), Theorem 2.2.
  3. ^ Allouche & Shallit (1992), Theorem 4.3.
  4. ^ Allouche & Shallit (1992), Theorem 4.4.
  5. ^ Schützenberger, M.-P. (1961), "On the definition of a family of automata", Information and Control, 4 (2–3): 245–270, doi:10.1016/S0019-9958(61)80020-X.
  6. ^ a b Allouche & Shallit (1992, 2003).
  7. ^ Berstel, Jean; Reutenauer, Christophe (1988). Rational Series and Their Languages. EATCS Monographs on Theoretical Computer Science. Vol. 12. Springer-Verlag. ISBN 978-3-642-73237-9.
  8. ^ Allouche & Shallit (1992), Example 8.
  9. ^ Allouche & Shallit (1992), Examples 3 and 26.
  10. ^ Allouche & Shallit (1992), Example 28.
  11. ^ Allouche & Shallit (1992), Theorem 2.3.
  12. ^ a b Allouche & Shallit (2003) p. 441.
  13. ^ Allouche & Shallit (1992), Theorem 2.5.
  14. ^ Allouche & Shallit (1992), Theorem 3.1.
  15. ^ Allouche & Shallit (2003) p. 445.
  16. ^ Allouche and Shallit (2003) p. 446.
  17. ^ Allouche and Shallit (2003) p. 441.
  18. ^ Bell, J. (2006). "A generalization of Cobham's theorem for regular sequences". Séminaire Lotharingien de Combinatoire. 54A.
  19. ^ Cobham, A. (1969). "On the base-dependence of sets of numbers recognizable by finite automata". Math. Systems Theory. 3 (2): 186–192. doi:10.1007/BF01746527. S2CID 19792434.
  20. ^ Allouche & Shallit (1992) Theorem 2.10.
  21. ^ Allouche and Shallit (2003) p. 444.
  22. ^ Allouche and Shallit (1993) p. 168–169.

References

[edit]